/**
*  @file Locate.c
 *  @desc 实现一种带“访问频度调整”机制的单循环链表：
 *        - 每次访问 locate(x) 后，节点的访问频度 `fre` 会 +1
 *        - 然后该节点会在链表中重新排序，保持链表按频度递减排序
 *        - 适用于“最近频繁使用”模式的动态数据维护（例如缓存）
 *  @author WangBlue (wangjiping596@gmail.com)
 *  @date 2025-08-04 17:17
 *  @version 1.0
 */


#include <stdio.h>
#include <stdlib.h>

// ======================== 链表节点结构 ========================

/**
 * @struct node
 * @brief 循环单链表节点
 *
 * - data：数据值
 * - fre ：访问频率（被 locate 函数访问次数）
 * - next：指向下一个节点的指针
 */
typedef struct node {
    int data;
    int fre;
    struct node *next;
} node, *link;

// ======================== 基础操作函数 ========================

/**
 * @brief 创建一个新节点（fre 初始为 1）
 * @param value 节点数据值
 * @return 返回新节点指针
 */
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;

    newNode->data = value;
    newNode->fre = 1;       // 初始访问频率为 1
    newNode->next = NULL;
    return newNode;
}

/**
 * @brief 初始化链表（带头节点，循环结构）
 * @param head 指向头节点指针的地址
 */
void initLink(link *head) {
    link newNode = createNode(0);  // 头节点不存有效数据
    if (newNode == NULL) return;

    newNode->next = newNode;       // 构成自环，形成循环
    *head = newNode;
}

/**
 * @brief 头插法插入一个新节点
 * @param head 链表头节点指针
 * @param value 要插入的数据值
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = head->next;
    head->next = newNode;
}

/**
 * @brief 打印链表中所有节点的值和访问频率（跳过头节点）
 * @param head 链表头
 */
void printList(link head) {
    if (head == NULL || head->next == head) return;

    link cur = head->next;
    while (cur != head) {
        printf("value is %d, fre is %d\n", cur->data, cur->fre);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * @brief 查找值为 x 的节点，访问频度 +1，并根据频率重新排序节点
 *
 * 操作过程：
 * 1. 找到值为 x 的节点
 * 2. 将其从原位置断开
 * 3. 增加其频率
 * 4. 插入到合适的新位置（保持频率降序）
 *
 * @param head 链表头
 * @param x 要查找的值
 */
void locate(link head, int x) {
    if (head == NULL || head->next == head) return;

    link cur = head->next;
    link pre = head;

    // 1. 查找值为 x 的节点
    while (cur != head && cur->data != x) {
        pre = cur;
        cur = cur->next;
    }

    if (cur == head) return; // 没找到，直接返回

    // 2. 删除当前节点（从当前位置断开）
    pre->next = cur->next;

    // 3. 访问频度 +1
    cur->fre++;

    // 4. 找到新的插入位置，按 fre 降序插入
    link temp = head->next;
    link insertPre = NULL;

    // 注意：fre 频度较大 → 应靠前
    while (temp != head && cur->fre < temp->fre) {
        insertPre = temp;
        temp = temp->next;
    }

    if (insertPre == NULL) {
        // 插入到链表最前面（第一个有效节点之前）
        cur->next = head->next;
        head->next = cur;
    } else {
        // 插入到 insertPre 后面
        cur->next = insertPre->next;
        insertPre->next = cur;
    }
}

int main() {
    link head = NULL;

    initLink(&head);        // 创建头节点
    istHead(head, 1);       // 插入元素
    istHead(head, 2);
    istHead(head, 3);
    istHead(head, 4);       // 链表初始为：4 -> 3 -> 2 -> 1

    locate(head, 1);        // 访问1，频度变为2
    locate(head, 2);        // 访问2，频度变为2
    locate(head, 2);        // 再次访问2，频度变为3
    locate(head, 1);        // 再次访问1，频度变为3

    // 此时频度排序应为：1(3) -> 2(3) -> 4(1) -> 3(1)
    printList(head);

    return 0;
}
